|
A finite state transducer (FST) is a finite state machine with two tapes: an input tape and an output tape. This contrasts with an ordinary finite state automaton (or finite state acceptor), which has a single tape. ==Overview== An automaton can be said to ''recognize'' a string if we view the content of its tape as input. In other words, the automaton computes a function that maps strings into the set . Alternatively, we can say that an automaton ''generates'' strings, which means viewing its tape as an output tape. On this view, the automaton generates a formal language, which is a set of strings. The two views of automata are equivalent: the function that the automaton computes is precisely the indicator function of the set of strings it generates. The class of languages generated by finite automata is known as the class of regular languages. The two tapes of a transducer are typically viewed as an input tape and an output tape. On this view, a transducer is said to ''transduce'' (i.e., translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape. It may do so nondeterministically and it may produce more than one output for each input string. A transducer may also produce no output for a given input string, in which case it is said to ''reject'' the input. In general, a transducer computes a relation between two formal languages. Each string-to-string finite state transducer relates the input alphabet Σ to the output alphabet Γ. Relations ''R'' on Σ *×Γ * that can be implemented as finite state transducers are called rational relations. Rational relations that are partial functions, i.e. that relate every input string from Σ * to at most one Γ *, are called rational functions. Finite-state transducers are often used for phonological and morphological analysis in natural language processing research and applications. Pioneers in this field include Ronald Kaplan, Lauri Karttunen, Martin Kay and Kimmo Koskenniemi. A common way of using transducers is in a so-called "cascade", where transducers for various operations are combined into a single transducer by repeated application of the composition operator (defined below). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Finite state transducer」の詳細全文を読む スポンサード リンク
|